​王小云院士：公钥密码学的数学基础（第二版）

密码学作为信息安全的支撑学科, 是一门起源十分古老而在近代得到极其广泛有效应用、正在蓬勃发展的新兴学科. 密码学的两个基本问题是：一是对信息加以保密, 要使第三方获得了加密的信息后, 也不知道信息的真实内容; 二是与此相对立的, 当第三方获得了加密的信息后, 可以设法破解从中获得信息的真实内容. 许许多多的方法都可以用于密码学, 对信息加以保密和破解, 数学一直是密码学的重要工具. 特别是提出公钥密码系统以来, 数学在密码学中的重要性取得了无可争辩的地位, 也可以说密码学从此成为数学中的一个独特学科.

自 1976 年 Diffie 和 Hellman 提出公钥密码的思想以来, 密码学家设计了多个具有代表性的公钥密码算法.这些密码算法的安全性均基于一些经典数学难题求解的困难性, 如因子分解问题、离散对数问题、背包问题以及格中的最短向量问题等. 而公钥密码算法分析的核心就是研究这些数学难题的快速求解算法.

王小云院士一直十分重视信息安全专业的人才培养和基础课的教材建设.《数论与代数结构》是密码学的一门重要基础课.为了更好地让信息安全专业的学生顺利学习、掌握现代密码学的基本理论, 深刻领会密码学与数学领域的学科交叉特点, 特编写了《公钥密码学的数学基础》作为信息安全专业的数学基础课教材. 该书所涉及的理论知识都是现代密码学特别是公钥密码学所需要的数学基础知识, 不仅可以作为信息安全专业本科生教学的教材,也是密码科技工作者必要的专业参考书.

本书第一版包含了现代密码学特别是公钥密码学所需要的数学基础知识, 本书不是初等数论和抽象代数的简单组合, 而是反映信息安全学科交叉特点, 并体现数学理论与密码应用相结合的教材. 该书的内容主要有以下三方面的特色. 一是数论与代数基本理论涵盖了一些重要的密码基础数学理论. 如作者既介绍辗转相除法、Euler 定理、孙子定理、原根等初等数论基本理论, 也讲述了在密码学中广泛使用的利用辗转相除法求最大公因子、求模逆模幂运算、离散对数、因子分解等密码基础数学理论. 二是注重理论与实践的紧密结合, 并突出实践. 在讲到比较重要的算法时, 作者都配备一定数量的实践题目, 使学生能体会到理论在实践中的应用. 三是将算法复杂性理论贯穿全书, 介绍与数论、代数基本理论相关的算法及其复杂性, 让读者初步体会数学理论在密码算法中的应用.

该书是经过山东大学信息安全专业教学中多次使用并反馈修改的结果, 这对本书的最终完成具有十分重要的意义.

第一版自 2013 年出版以来受到广泛欢迎, 获得首届全国教材建设奖全国优秀教材 (高等教育类) 二等奖. 第二版在第一版的基础上修订了若干疏误, 此外更新添加了一些内容, 主要包括:

(1) 添加第 5, 10, 11 三章的习题.

(2) 具体计算对于本书内容的理解和应用是有益的. 作者以计算软件 Sage-Math为例, 在除第 7 章外的其余十章添加计算示例, 方便读者参考并使用自己选择的计算软件进行验证和实验.

(3) 第 10 章更新了利用快速傅里叶变换计算整数乘法的复杂度和 RSA 模数的分解记录, 添加利用大衍求一术求解模逆的算法介绍.

(4) 第 11 章添加了后量子密码的背景说明, 扩充了格相关计算问题的介绍.

(5) 本书在大部分章节和重要知识点处添加了对应的讲解视频, 读者可以扫描二维码观看.

王小云 王明强 孟宪萌 庄金成 著

北京：科学出版社，2022.12

ISBN 978-7-03-073111-1

责任编辑: 胡庆家 贾晓瑞

↑点击图片 购买本书↑

目录速览

第二版前言

第一版序
第一版前言
第1章 整除 1
1.1 整除的概念 1
1.2 最大公因子与最小公倍数 5
1.3 Euclid算法 10
1.4 求解一次不定方程——Euclid算法应用之一 13
1.5 整数的素分解 14
1.6 使用SageMath进行整除相关的计算 20
习题1 21
第2章 同余 23
2.1 同余的基本概念和基本性质 23
2.2 剩余类与剩余系 26
2.3 Euler定理 31
2.4 Wilson定理 34
2.5 使用SageMath进行同余相关的计算 37
习题2 38

第3章 同余方程 40
3.1 一元高次同余方程的概念 40
3.2 一次同余方程 43
3.3 一次同余方程组与孙子定理 44
3.4 一般同余方程 47
3.5 二次剩余 49
3.6 Legendre符号与acobi符号 52
3.7 使用SageMath求解同余方程 59
习题3 59

第4章 指数与原根 61
4.1 指数及其性质 61
4.2 原根及其性质 64
4.3 指标、既约剩余系的构造 67
4.4 n次剩余 72
4.5 使用SageMath进行指数与原根相关的计算 75
习题4 76

第5章 素数分布的初等结果 78
5.1 素数的基本性质与分布的主要结果介绍 78
5.2 Euler恒等式的证明 81
5.3 弱形式素数定理的证明 83
5.4 素数定理的等价命题 90
5.5 使用SageMath进行素数分布相关的计算 93
习题5 94

第6章 简单连分数 95
6.1 简单连分数及其基本性质 95
6.2 实数的简单连分数表示 98
6.3 连分数在密码学中的应用——对RSA算法的低解密指数攻击 103
6.4 使用SageMath进行简单连分数相关的计算 104
习题6 105

第7章 近世代数基本概念 106
7.1 映射 106
7.2 代数运算 109
7.3 带有运算集合之间的同态映射与同构映射 111
7.4 等价关系与分类 112
习题7 113

第8章 群论 114
8.1 群的定义 114
8.2 循环群 116
8.3 子群、子群的陪集 117
8.4 同态基本定理 121
8.5 有限群的实例 124
8.6 使用SageMath进行群论相关的计算 127
习题8 128

第9章 环与域 129
9.1 环的定义 129
9.2 整环、域、除环 131
9.3 子环、理想、环的同态 135
9.4 孙子定理的一般形式 140
9.5 欧氏环 142
9.6 有限域 144
9.7 商域 145
9.8 使用SageMath进行环与域相关的计算 148
习题9 151

第10章 公钥密码学中的数学问题 152
10.1 时间估计与算法复杂性 152
10.2 素检测 158
10.3 分解因子问题 160
10.4 RSA问题与强RSA问题 161
10.5 二次剩余 162
10.6 离散对数问题 164
10.7 使用SageMath求解公钥密码学中的数学问题 166
习题10 167

第11章 格的基本知识 168
11.1 基本概念 168
11.2 格相关的计算问题 169
11.3 格基约化算法 171
11.4 LLL算法应用 173
11.5 使用SageMath进行格相关的计算 179
习题11 179
参考文献 181

作者简介
王小云, 博士, 1966 年出生, 1983 年至1993年就读于山东大学数学系,先后获得学士、硕士和博士学位, 博士生导师为潘承洞教授. 现为清华大学高等研究院“杨振宁讲座”教授, 山东大学网络空间安全学院院长, 中国科学院院士, 发展中国家科学院院士 (TWAS Fellow), 国际密码协会会士 (IACRFellow), 中国密码学会理事长, 中国数学会副理事长. 主要从事密码理论及相关数学问题研究. 在密码分析领域, 提出了密码Hash函数的碰撞攻击理论, 破解了包括 MD5、SHA-1 在内的 5 个国际通用Hash函数算法; 在密码设计领域,主持设计的 Hash 函数 SM3 为国家密码算法标准, 并于 2018 年10 月正式成为 ISO/IEC 国际标准. 代表性论文50 余篇, 3 篇获欧密会、美密会最佳论文.曾获国家科技进步奖一等奖、国家自然科学奖二等奖、陈嘉庚科学奖、求是杰出科学家奖、苏步青应用数学奖、未来科学大奖——数学与计算机科学奖等.王明强, 博士, 1970 年生, 2004 年于山东大学数学系获得博士学位. 现为山东大学教授,博士生导师. 主要研究方向是计算数论, 后量子密码算法的分析、设计.孟宪萌, 博士, 1971 年生, 2002 年于山东大学数学系获得博士学位. 现为山东财经大学教授, 主要研究方向是数论与公钥密码理论.庄金成, 博士, 1987 年生, 2014 年于俄克拉荷马大学获得博士学位. 现为山东大学教授, 博士生导师. 主要研究方向是算法数论与后量子密码学.

精彩样章展示

左右滑动查看更多

购书链接

京东

当当网

（本期编辑：王芳）

更多教学服务

关注微信公众号“科学EDU”

近期文章：